package leetCode;

public class QuickSort {
    public static void quickSort(int nums[],int L,int R){

        if (L < R) {
            swap(nums,R,(int)(Math.random()*(R-L+1)));
            int []p=merge(nums,L,R);
            quickSort(nums,L,p[0]-1);
            quickSort(nums,p[1]+1,R);
        }
    }
    public static int[] merge(int nums[],int L,int R){
        int less=L-1;
        int more=R;
        while(L<more){
            if(nums[L]<nums[R]){
                swap(nums,++less,L++);
            }else if(nums[L]>nums[R]){
                swap(nums,--more,L);
            }else
                L++;
        }
        swap(nums,more,R);
        return new int[]{less+1,more};
    }
    public static void swap(int arr[],int a,int b){
       int temp=arr[a];
       arr[a]=arr[b];
       arr[b]=temp;
    }
}
